package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 覃国强
 * @date 2022-07-12 17:41
 */
public class 题库_0230_二叉搜索树中第K小的元素 {

  public static void main(String[] args) {
    TreeNode root1 = new TreeNode(1);
    TreeNode root2 = new TreeNode(2);
    TreeNode root3 = new TreeNode(3);
    TreeNode root4 = new TreeNode(4);


    root3.left = root1;
    root3.right = root4;
    root1.right = root2;

    Solution solution = new Solution();
    System.out.println(solution.kthSmallest(root3, 1));

  }


  static
  class Solution {
    public int kthSmallest(TreeNode root, int k) {
      Deque<TreeNode> stack = new ArrayDeque<>();

      while (root != null || !stack.isEmpty()) {
        if (root != null) {
          stack.push(root);
          root = root.left;
        } else {
          root = stack.pop();
          if (--k == 0) {
            break;
          }
          root = root.right;
        }
      }

      return root.val;
    }
  }

}
